//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 10⁵] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 栈 递归 链表 双指针 👍 1195 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    /*
        在leetcode网站提交没有问题, 因为是使用了额外的容器来进行记录辅助, 所以结果为:
        执行用时：252 ms, 在所有 C++ 提交中击败了7.34%的用户
        内存消耗：120.5 MB, 在所有 C++ 提交中击败了30.23%的用户
        通过测试用例：85 / 85
     */
    bool isPalindrome(ListNode* head) {
        int isPalindrome = true;
        std::stack<int> stack;

        ListNode* cur = head;
        while (cur != nullptr) {
            stack.push( cur->val );
            cur = cur->next;
        }

        cur = head;
        while (cur != nullptr) {
            if (stack.top() != cur->val) {
                isPalindrome = false;
                break;
            }
            stack.pop();
            cur = cur->next;
        }

        return isPalindrome;
    }

    /*
    使用双指针(快慢指针)。
     快指针每次走两步, 慢指针每次走一步。
     快指针走完的时候, 慢指针走到中点的位置。

     这个版本在 leetcode 执行和提交都是没有问题的。
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        int isPalindrome = true;

        //region 使用快慢指针。
        // 注意: 下面的代码是一个最优的写法...

        // right 为慢指针。这里是一个针对这个题的写法。
        // 如果是一般的写法就是 ListNode* slowPtr = head;
        // 写成 ListNode* slowPtr = head->next; 的原因是下面的while执行完之后, slowPtr就直接指向了
        // 右部分的第一个结点。
        ListNode* right = head->next;
        // cur 为快指针。
        ListNode* cur = head;
        // 找到中间结点。
        while (cur->next != nullptr && cur->next->next != nullptr) {
            right = right->next;
            cur = cur->next->next;
        }
        // ... 背也要背下来。
        //endregion


        std::stack<int> stack;
        while (right != nullptr) {
            stack.push( right->val );
            right = right->next;
        }

        while (!stack.empty()) {
            if (head->val != stack.top()) {
                return false;
            }
            stack.pop();
            head = head->next;
        }

        return isPalindrome;
    }

    /*
     * 这个是我自己写的版本。在 leetcode 执行成功, 但是提交就失败了。
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        int isPalindrome = true;

//        ListNode* slowPtr = head;
//        ListNode* fastPtr = head;
//        // 找到中间结点。
//        while (slowPtr->next != nullptr && fastPtr->next->next != nullptr) {
//            slowPtr = slowPtr->next;
//            fastPtr = fastPtr->next->next;
//        }

        ListNode* slowPtr = head->next;
        // cur 为快指针。
        ListNode* fastPtr = head;
        // 找到中间结点。
        while (slowPtr->next != nullptr && fastPtr->next->next != nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }


        // 右边界的第一个结点:
//        ListNode* rightRegion = slowPtr->next;
        ListNode* rightRegion = slowPtr;

        std::stack<int> stack;
        while (rightRegion != nullptr) {
            stack.push( rightRegion->val );
            rightRegion = rightRegion->next;
        }

        ListNode* leftRegion = head;
        while (!stack.empty()) {
            if (leftRegion->val != stack.top()) {
                isPalindrome = false;
            }
            stack.pop();
            leftRegion = leftRegion->next;
        }

        return isPalindrome;
    }


    /*
     * 将正确的重构, 看提交行不行。
     * 提交通过了。
     *
     * 下面的函数继续对这个算法进行重构。
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        int isPalindrome = true;

        //region 使用快慢指针。
        ListNode* slowPtr = head->next;
        ListNode* fastPtr = head;
        // 找到中间结点。
        while (fastPtr->next != nullptr && fastPtr->next->next != nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        // ... 背也要背下来。
        //endregion


        std::stack<int> stack;
        ListNode* rightRegion = slowPtr;
        while (rightRegion != nullptr) {
            stack.push( rightRegion->val );
            rightRegion = rightRegion->next;
        }

        ListNode* leftRegion = head;
        while (!stack.empty()) {
            if (leftRegion->val != stack.top()) {
                isPalindrome = false;
                break;
            }
            stack.pop();
            leftRegion = leftRegion->next;
        }


        return isPalindrome;
    }


    /*
     * 重构正确的最终的版本。
     *
     * 这个版本是没有问题的, 提交是通过的。
     *
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        bool isPalindrome = true;

        /*
         * todo 笔记: 通过快慢双指针来确定链表的中间结点。
         *  这种写法非常的重要, 背过！
         *  但是我觉得是有问题的。
         *  例如: {1 -> 2 -> 1 -> nullptr}
         *  或者是这个
         *  {1 -> 2 -> 3 -> 2 -> 1 -> nullptr}
         *  即 链表的长度为 奇数的时候, 此时 while()循环的判断条件 fast->next 就已经是 nullptr了,
         *  但是判断条件是 fast->next->next, 我就是不理解, 为什么 nullptr可以访问next的?
         */
        //region 使用快慢指针。
//        ListNode* slowPtr = head->next;
        ListNode* slowPtr = head;
        ListNode* fastPtr = head;
        // 找到中间结点。
        while (slowPtr->next != nullptr && fastPtr->next->next != nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        // ... 背也要背下来。
        //endregion


        std::stack<int> stack;

//        ListNode* rightRegion = slowPtr;
        ListNode* rightRegion = slowPtr->next;
        while (rightRegion != nullptr) {
            stack.push( rightRegion->val );
            rightRegion = rightRegion->next;
        }

        ListNode* leftRegion = head;
        while (!stack.empty()) {
            if (leftRegion->val != stack.top()) {
                isPalindrome = false;
                break;
            }
            stack.pop();
            leftRegion = leftRegion->next;
        }


        return isPalindrome;
    }


    /*
     * 我睡了一宿后, 再写一下。失败, 心态崩了。算了。继续第三种解法了。
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        bool isPalindrome = true;
        using Node = ListNode;

        Node* slowPtr = head;
        Node* fastPtr = head;
        while (slowPtr->next != nullptr && fastPtr->next->next != nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        Node* rightRegion = slowPtr->next;
        Node* leftRegion = head;

        std::stack<int> help;
        while (rightRegion != nullptr) {
            help.push( rightRegion->val );
            rightRegion = rightRegion->next;
        }

        while (!help.empty()) {
            if (help.top() != leftRegion->val) {
                isPalindrome = false;
            }
            help.pop();
            leftRegion = leftRegion->next;
        }

        return isPalindrome;
    }


    /*
     * 第 3 种解法。真的离谱WC。
     * todo 笔记: WC, 我之前的找到链表中间结点的while循环的条件一直是错误的。只判断
     *  fastPtr->next 和 fastPtr->next->next 就可以了！！
     *  真的一定要细心, 一步一步来。
     *  提交通过了。WC, 真的折磨人！
     */
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        bool isPalindrome = true;
        using Node = ListNode;

        Node* slowPtr = head;
        Node* fastPtr = head;
        while (fastPtr->next != nullptr && fastPtr->next->next != nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        // rightRegion是右部分的第一个结点。
        Node* rightRegion = slowPtr->next;
        Node* leftRegion = head;

        // 将右半部分逆序。
        // 双指针解决。pre, cur。
        Node* pre = nullptr;
        Node* cur = rightRegion;
        while (cur != nullptr) {
            Node* tmp = cur->next;

            cur->next = pre;

            pre = cur;
            cur = tmp;
        }
        rightRegion = pre;
        // 然后右部分已经逆序了。


        while (leftRegion != nullptr && rightRegion != nullptr) {
            if (leftRegion->val != rightRegion->val) {
                isPalindrome = false;
                break;
            }
            leftRegion = leftRegion->next;
            rightRegion = rightRegion->next;
        }

        // 将右部分再逆序回来。
        pre = nullptr;
        cur = slowPtr->next;
        while (cur != nullptr) {
            Node* tmp = cur->next;

            cur->next = pre;

            pre = cur;
            cur = tmp;
        }
        rightRegion = pre;

        slowPtr->next = rightRegion;

        return isPalindrome;
    }

};
//leetcode submit region end(Prohibit modification and deletion)
